package com.demo.java.OD1_50.OD46;

import java.util.Scanner;
import java.util.TreeSet;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【考古学家】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145580040
 */
public class OdMain {
    public static final TreeSet<String> resTreeSet = new TreeSet<>();  // 用于存储并自动排序排列结果

    // 生成全排列的递归函数
    public static void solve(int index, String[] parts) {
        if (index == parts.length) {  // 当索引达到字符串数组的末尾时，说明一个排列已经生成
            StringBuilder sb = new StringBuilder();
            for (String str : parts) {  // 将排列的字符组合成一个字符串
                sb.append(str);
            }
            if (!sb.toString().isEmpty()) {  // 防止空字符串
                resTreeSet.add(sb.toString());  // 将排列加入结果集，TreeSet 自动去重并排序
            }
            return;
        }
        for (int i = index; i < parts.length; ++i) {  // 遍历字符数组
            dataSwap(i, index, parts);  // 交换字符，生成新的排列
            solve(index + 1, parts);  // 递归处理下一个字符
            dataSwap(i, index, parts);  // 回溯，恢复原排列
        }
    }

    // 交换数组中的两个字符
    public static void dataSwap(int i, int j, String[] values) {
        String temp = values[j];
        values[j] = values[i];
        values[i] = temp;
    }

    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(System.in);
            int n = Integer.parseInt(s.nextLine());  // 读取 N
            String part = s.nextLine();  // 读取字符序列
            String[] parts = part.split(" ");  // 将字符序列分割为数组
            solve(0, parts);  // 调用递归生成所有排列
            for (String str : resTreeSet) {  // 遍历输出所有排列
                System.out.println(str);
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");  // 异常处理
        }
    }
}